package datastruct;

import java.util.HashMap;
import java.util.Map;

public class LRUCache146 {
    Map<Integer, Node> map;
    Node head; // dummy head
    Node tail; // dummy tail
    int capacity;

    public static class Node {
        public Integer key;
        public Integer value;
        public Node next;
        public Node prev;

        public Node(Integer key, Integer value, Node next, Node prev) {
            this.key = key;
            this.value = value;
            this.next = next;
            this.prev = prev;
        }
    }

    public LRUCache146(int capacity) {
        this.map = new HashMap<>(capacity);
        this.head = new Node(null, null, null, null);
        this.tail = new Node(null, null, null, null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        } else {
            removeNode(node);
            addFirst(node);
            return node.value;
        }
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            node = new Node(key, value, null, null);
            map.put(key, node);
            addFirst(node);
            if (map.size() > capacity) {
                map.remove(tail.prev.key);
                removeNode(tail.prev);
            }
        } else {
            node.value = value;
            removeNode(node);
            addFirst(node);
        }
    }

    public void addFirst(Node node) {
        Node next = head.next;

        node.prev = head;
        node.next = next;

        next.prev = node;
        head.next = node;
    }

    public void removeNode(Node node) {
        Node next = node.next;
        Node prev = node.prev;

        next.prev = prev;
        prev.next = next;

        // clear links
        node.next = null;
        node.prev = null;
    }
}
